package cn.dlc.com.graph;

import cn.dlc.com.queue.Queue;
import cn.dlc.com.stack.Stack;
import lombok.Data;

/**
 * @author 邓立川
 * @date 2021/3/30 7:17
 * @desc 深度优先搜索算法获取某个顶点到指定顶点的路径
 */
@Data
public class DepthFirstPaths {

    // 索引代表顶点，值表示当前顶点是否已经被搜索
    private boolean[] marked;
    // 起点
    private int s;

    // 索引代表顶点，值代表从起点s到当前顶点路径上的最后一个顶点
    private int[] edgeTo;

    public DepthFirstPaths(Graph G, int s){
        this.marked = new boolean[G.getV()];
        this.s = s;

        // 获取长度
        this.edgeTo = new int[G.getV()];
        dfs(G, s);
    }

    // 通过深度遍历，获取和当前顶点相通的所有节点
    private void dfs(Graph G, int v){
        // 当前节点标记为一搜索
        this.marked[v] = true;

        // 获取当前节点的邻接链表
        Queue<Integer> adj = G.adj(v);
        for (Integer w : adj) {
            if(!marked[w]) {
                dfs(G, w);
                // 同时将这条边放到edgeTo里面去，指向上一个节点
                edgeTo[w] = v;
            }
        }
    }

    // 判断w顶点与当前顶点是否存在路径
    public boolean hasPathTo(int w) {
        // 判断有没有找到过这个节点，找到过，表示存在路径
        return marked[w];
    }

    //找出从当前顶点到顶点v的路径(就是该路径经过的顶点)
    public Stack<Integer> pathTo(int v) {
        // 如果不存在路径
        if(!hasPathTo(v)) {
            return null;
        }

        Stack<Integer> stack = new Stack<>();
        // 从顶点v开始找，一直找到起点s
        for (int x = v; x != s ; x = edgeTo[x]) {
            // 初始为当前v节点，每次从edgeTo中获取上一个节点
            // 因为edgeTo里面存放的就是上一个节点的信息
            // 添加到栈里面
            stack.push(x);
        }

        // 起点也放到栈里面
        stack.push(this.s);

        return stack;
    }
}
